import java.util.LinkedList;
import java.util.Queue;

/**
 * 1162. 地图分析
 * https://leetcode-cn.com/problems/as-far-from-land-as-possible/
 */
public class Solutions_1162 {
    public static void main(String[] args) {
//        int[][] grid = {{1, 0, 1},
//                        {0, 0, 0},
//                        {1, 0, 1}};  // output: 2

        int[][] grid = {{1, 0, 0, 0},
                        {0, 0, 0, 0},
                        {0, 0, 0, 0},
                        {1, 0, 0, 1}};  // output: 3

//        int[][] grid = {{1, 0, 0},
//                        {0, 0, 0},
//                        {0, 0, 0}};  // output: 4

        int result = maxDistance(grid);
        System.out.println(result);
    }

    /**
     * 区别于一个源头的 BFS，该题使用的是多源 BFS
     * 将每个陆地都看做是 BFS 的起点，逐层扩展
     * - 以陆地为起点，将距离为 1 的位置（上、下、左、右）上的海洋坐标加入队列
     * - 在以上基础上，再以海洋为起点，将与其距离为 1 的位置上的海洋坐标加入队列
     * ...
     * 每扩散一层后，若队列中元素不为空，说明有海洋坐标存在
     * 可以理解为：每一批队列中的坐标点，就是与每个陆地相同距离的海洋坐标
     * 例：1  0  0  0
     *    0  0  0  0
     *    0  0  0  0
     *    1  0  0  1   res = 3
     * 演算过程：
     * 1. 3 块陆地入队：{{0, 0}, {3, 0}, {3, 3}}
     * 2. 距离 1：与陆地距离为 1 的海洋入队：{{0, 1}, {1, 0}, {2, 0}, {3, 1}, {3, 2}, {2, 3}}
     * 3. 距离 2：与距离 1 批次中的距离为 1 的海洋入队：{{0, 2}, {1, 1}, {2, 1}, {2, 2}, {1, 3}}
     * 4. 距离 3：与距离 2 批次中的距离为 1 的海洋入队：{{0, 3}, {1, 2}}
     * 5. 距离 4：通过距离 3，找不到距离为 1 的海洋了（找到过的海洋，都被标记过）
     * 6. 故最远距离为 3
     */
    public static int maxDistance(int[][] grid) {
        int row = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < row; j++) {
                if (grid[i][j] == 1) {
                    // 陆地加入到队列中
                    queue.add(new int[]{i, j});
                }
            }
        }
        int res = 0;
        if (queue.isEmpty() || queue.size() == row * row) {
            // 队列中没有陆地，或者 grid 中全是陆地的情况，将无法计算
            return res;
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 范围扩散一层，即所在位置的上、下、左、右位置
                int[] arr = queue.poll();
                int r = arr[0];
                int c = arr[1];
                // 上
                if (r > 0 && grid[r - 1][c] == 0) {
                    // 标记状态并添加到队列中
                    grid[r - 1][c] = 2;
                    queue.add(new int[]{r - 1, c});
                }
                // 下
                if (r < row - 1 && grid[r + 1][c] == 0) {
                    // 标记状态并添加到队列中
                    grid[r + 1][c] = 2;
                    queue.add(new int[]{r + 1, c});
                }
                // 左
                if (c > 0 && grid[r][c - 1] == 0) {
                    // 标记状态并添加到队列中
                    grid[r][c - 1] = 2;
                    queue.add(new int[]{r, c - 1});
                }
                // 右
                if (c < row - 1 && grid[r][c + 1] == 0) {
                    // 标记状态并添加到队列中
                    grid[r][c + 1] = 2;
                    queue.add(new int[]{r, c + 1});
                }
            }
            if (!queue.isEmpty()) {
                // 本次扩散，能够搜索到海洋
                res ++;
            }
        }
        return res;
    }
}
